<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    81. Search in Rotated Sorted Array II
   </h1>
   <p>
    Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
   </p>
   <p>
    (i.e.,
    <code>
     [0,0,1,2,2,5,6]
    </code>
    might become
    <code>
     [2,5,6,0,0,1,2]
    </code>
    ).
   </p>
   <p>
    You are given a target value to search. If found in the array return
    <code>
     true
    </code>
    , otherwise return
    <code>
     false
    </code>
    .
   </p>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> nums = [2<code>,5,6,0,0,1,2]</code>, target = 0
<strong>Output:</strong> true
</pre>
   <p>
    <strong>
     Example 2:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> nums = [2<code>,5,6,0,0,1,2]</code>, target = 3
<strong>Output:</strong> false</pre>
   <p>
    <strong>
     Follow up:
    </strong>
   </p>
   <ul>
    <li>
     This is a follow up problem to&nbsp;
     <a href="/problems/search-in-rotated-sorted-array/description/">
      Search in Rotated Sorted Array
     </a>
     , where
     <code>
      nums
     </code>
     may contain duplicates.
    </li>
    <li>
     Would this affect the run-time complexity? How and why?
    </li>
   </ul>
  </div>
  <div>
   <h1 class="question_title">
    81. 搜索旋转排序数组 II
   </h1>
   <p>
    假设按照升序排序的数组在预先未知的某个点上进行了旋转。
   </p>
   <p>
    ( 例如，数组&nbsp;
    <code>
     [0,0,1,2,2,5,6]
    </code>
    &nbsp;可能变为&nbsp;
    <code>
     [2,5,6,0,0,1,2]
    </code>
    &nbsp;)。
   </p>
   <p>
    编写一个函数来判断给定的目标值是否存在于数组中。若存在返回&nbsp;
    <code>
     true
    </code>
    ，否则返回&nbsp;
    <code>
     false
    </code>
    。
   </p>
   <p>
    <strong>
     示例&nbsp;1:
    </strong>
   </p>
   <pre><strong>输入:</strong> nums = [2<code>,5,6,0,0,1,2]</code>, target = 0
<strong>输出:</strong> true
</pre>
   <p>
    <strong>
     示例&nbsp;2:
    </strong>
   </p>
   <pre><strong>输入:</strong> nums = [2<code>,5,6,0,0,1,2]</code>, target = 3
<strong>输出:</strong> false</pre>
   <p>
    <strong>
     进阶:
    </strong>
   </p>
   <ul>
    <li>
     这是
     <a href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array/description/">
      搜索旋转排序数组
     </a>
     &nbsp;的延伸题目，本题中的&nbsp;
     <code>
      nums
     </code>
     &nbsp; 可能包含重复元素。
    </li>
    <li>
     这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
    </li>
   </ul>
  </div>
 </body>
</html>